package com.coder.algorithm.leetcode

/**
 * [5. 最长回文子串](https://leetcode-cn.com/problems/longest-palindromic-substring)
 *
 * @author yuhus
 * @date: 2022/3/15
 */
class l_0005 {

    /**
     * 找到回文中心点 i，则：
     * s[i] = s[i+1] 或者 s[i-1] = s[i+1]
     * 在s的前面和每个字符后面都加入一个特殊字符，则只需要判断：
     * s[i-1] = s[i+1] 情况，步进为2
     */
    fun longestPalindrome(s: String): String {
        if (s.length <= 1) {
            return s
        }
        var longest = s.substring(0, 1)
        for (i in s.indices) {
            if (i+1 < s.length && s[i] == s[i + 1]) {
                val temp = longestPalindromeWithCenter(s, i, i + 1)
                if (temp.length > longest.length) {
                    longest = temp
                }
            } else if (i - 1 >= 0 && i + 1 < s.length && s[i - 1] == s[i + 1]) {
                val temp = longestPalindromeWithCenter(s, i - 1, i + 1)
                if (temp.length > longest.length) {
                    longest = temp
                }
            }
        }
        return longest
    }

    private fun longestPalindromeWithCenter(s: String, l: Int, r: Int): String {
        var start = l
        var end = r
        // 相邻，找右边界
        if (l + 1 == r) {
            while (end < s.length && s[l] == s[end]) {
                end++
            }
            end--
        }
        while (start >= 0 && end < s.length && s[start] == s[end]) {
            start--
            end++
        }
        return s.substring(start + 1, end)
    }

    /**
     * 遍历所有子字符串，判断是否是回文
     * 可以简化为动态规划
     */
    fun longestPalindrome_solution1(s: String): String {
        var start = 0
        var end = 0
        var length = 0
        for (i in 0..s.length) {
            for (j in 0 until i) {
                if (isPalindrome(s.substring(j, i))) {
                    if (i - j > length) {
                        length = i - j
                        start = j
                        end = i
                    }
                }
            }
        }
        return s.substring(start, end)
    }

    private fun isPalindrome(s: String): Boolean {
        var low = 0
        var high = s.length - 1
        while (low <= high) {
            if (s[low] != s[high]) {
                return false
            }
            low++
            high--
        }
        return true
    }

    companion object {
        @JvmStatic
        fun main(args: Array<String>) {
            val s = "babad"
            println(s.substring(1, 4))
        }
    }
}